package com.leetcode;

/**
 * 88. 合并两个有序数组
 * 使用正序, 并且借助辅助数组存储
 *
 * @author fy
 * @date 2022/4/20 21:10
 */
public class Solution88_1 {

    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if (nums1 == null || nums2 == null) {
            throw new RuntimeException("num1 or nums2 is null");
        }
        if (nums1.length != (m + n)) {
            throw new RuntimeException("nums1.length: " + nums1.length + " is not m + n: " + (m + n));
        }
        if (nums2.length != n) {
            throw new RuntimeException("nums2.length: " + nums2.length + " is not n: " + n);
        }
        int length = m + n;
        int[] tmp = new int[length];
        int index1 = 0;
        int index2 = 0;
        int index = 0;
        while (index1 < m && index2 < n) {
            if (nums1[index1] <= nums2[index2]) {
                tmp[index++] = nums1[index1++];
            } else {
                tmp[index++] = nums2[index2++];
            }
        }
        while (index1 < m) {
            tmp[index++] = nums1[index1++];
        }
        while (index2 < n) {
            tmp[index++] = nums2[index2++];
        }

        for (int i = 0; i < length; i++) {
            nums1[i] = tmp[i];
        }
    }

    public static void main(String[] args) {
        int[] nums1 = new int[]{1, 2, 3, 0, 0, 0};
        int[] nums2 = new int[]{2, 5, 6};
        int m = 3;
        int n = 3;
        new Solution88_1().merge(nums1, m, nums2, n);
        for (int num : nums1) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

}
